//
//  LinkList_7.swift
//  LinkTest_7
//
//  Created by xiangzuhua on 2020/9/22.
//  Copyright © 2020 wangzh. All rights reserved.
//

import UIKit

public class ListNode: NSObject {
    public var val: Int
    public var next: ListNode?
    public init(_ val:Int) {
        self.val = val
        self.next = nil
    }
}

public class LinkList_7: NSObject {
    // 单链表反转一
    class func reversalList(_ head:ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        var newHead: ListNode? = ListNode.init(0).next
        var p = head
        while p != nil {
            let temp = p?.next
            p?.next = newHead
            newHead = p
            p = temp
        }
        return newHead
    }
    // 单链表反转二
    class func recursionReversalList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        
        let newHead = recursionReversalList(head?.next)
        head?.next?.next = head
        head?.next = nil
        return newHead
    }
    
    // 链表中环的检测
    class func hasCycleList(_ head: ListNode?) -> Bool {
        if head == nil || head?.next == nil {
            return false
        }
        
        var fast: ListNode? = head
        var slow: ListNode? = head
        while slow != nil && fast != nil && fast?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
            if fast == slow {
                return true
            }
        }
        return false
    }
    
    // 两个有序链表合并为一个有序链表一
    class func mergeTowList(_ l1: ListNode?,_ l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        }
        if l2 == nil {
            return l1
        }
        
        var newList = ListNode.init(0)
        var p = newList
        var templ1 = l1
        var templ2 = l2
        while templ1 != nil && templ2 != nil {
            if templ1!.val < templ2!.val {
                newList.next = templ1
                templ1 = templ1?.next
            } else {
                newList.next = templ2
                templ2 = templ2?.next
            }
            newList = newList.next!
        }
        
        if templ1 == nil {
            newList.next = templ2
        } else {
            newList.next = templ1
        }
        p = p.next ?? p
        return p
    }
    
    // 两个有序链表合成一个有序链表二
    class func recurionMergeTwoList(l1: ListNode?,l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        }
        if l2 == nil {
            return l1
        }
        
        if l1!.val < l2!.val {
            l1?.next = recurionMergeTwoList(l1: l1!.next, l2: l2)
            return l1
        }else{
            l2?.next = recurionMergeTwoList(l1: l1, l2: l2!.next)
            return l2
        }
    }
    
    // 删除链表倒数第n个节点
    class func removeNthFromeEnd(_ head: ListNode?,n: Int) -> ListNode? {
        guard let head = head else{
            return nil
        }
        let dummy = ListNode.init(0)
        dummy.next = head
        var prev: ListNode? = dummy
        var post: ListNode? = dummy
        for _ in 0..<n{
            if post == nil {
                return dummy.next
            }
            post = post!.next
        }
        
        while post != nil && post?.next != nil {
            prev = prev!.next
            post = post!.next
        }
        
        // 删除节点
        prev!.next = prev!.next!.next
        return dummy.next
    }
    
    // 求链表的中间节点
    class func findCenterNode(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        var startNode:ListNode? = head
        var nextNode: ListNode? = head
        while nextNode != nil && nextNode?.next != nil{
            startNode = startNode?.next
            nextNode = nextNode?.next?.next
        }
        return startNode
    }
    
    
}




